Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

摘要

We prove that any algorithm for learning parities requires either a memory ofquadratic size or an exponential number of samples. This proves a recentconjecture of Steinhardt, Valiant and Wager and shows that for some learningproblems a large storage space is crucial. More formally, in the problem of parity learning, an unknown string $x \in\{0,1\}^n$ was chosen uniformly at random. A learner tries to learn $x$ from astream of samples $(a_1, b_1), (a_2, b_2) \ldots$, where each~$a_t$ isuniformly distributed over $\{0,1\}^n$ and $b_t$ is the inner product of $a_t$and $x$, modulo~2. We show that any algorithm for parity learning, that usesless than $\frac{n^2}{25}$ bits of memory, requires an exponential number ofsamples. Previously, there was no non-trivial lower bound on the number of samplesneeded, for any learning problem, even if the allowed memory size is $O(n)$(where $n$ is the space needed to store one sample). We also give an application of our result in the field of bounded-storagecryptography. We show an encryption scheme that requires a private key oflength $n$, as well as time complexity of $n$ per encryption/decription of eachbit, and is provenly and unconditionally secure as long as the attacker usesless than $\frac{n^2}{25}$ memory bits and the scheme is used at most anexponential number of times. Previous works on bounded-storage cryptographyassumed that the memory size used by the attacker is at most linear in the timeneeded for encryption/decription.